package book;

import java.util.Arrays;
import java.util.Stack;

public class LIS_Solution {
    // 求最长递增子序列 (Longest Increasing Subsequence, LIS)
    int LIS(int[] a) {
        // dp[i] 储存以a[i]为结尾的最长递增子序列的长度
        // 对于每个数字，其本身就是长度为1的递增子序列，因此初始化为1
        int[] dp = new int[a.length];
        Arrays.fill(dp, 1);
        // last[i] 储存以a[i]为结尾的最长递增子序列中，对应上一个数字的下标位置
        // 根据最优性原理，上一个数字也位于以该数字结尾的最长递增子序列中
        // 因此，我们依次往前查找，就能构建出整个最长递增子序列
        int[] last = new int[a.length];
        Arrays.fill(last, -1); // 初始化-1表示当前已经是序列第一个数字

        int max_i = 0; // 维护当前储存了最长子序列的位置

        // 动态规划：我们从第二个数字开始依次完成填表
        for (int i = 1; i < a.length; i++) {
            // 对于len[i]，遍历i前面的结果，尝试找到最大的len[j] + 1 = len[i]
            for (int j = 0; j < i; j++) 
                if (a[j] < a[i]) // 首先判断是否满足递增的要求
                    if (dp[j] + 1 > dp[i]) { // 然后判断是否找到更大的结果
                        // 找到更优的结果并更新状态
                        dp[i] = dp[j] + 1;
                        last[i] = j;
                        if (dp[i] > dp[max_i])
                            max_i = i;
                    }
        }

        // 填表完毕，输出结果
        // 留意last数组是从后往前存储的，我们使用栈进行顺序调整
        Stack<Integer> stack = new Stack<>();
        for (int i = max_i; i >= 0; i = last[i]) 
            stack.push(i);
        System.out.print("最长递增子序列是:");
        while (!stack.empty())
            System.out.print(" " + a[stack.pop()]);
        System.out.println();

        // 返回最长递增子序列的长度
        return dp[max_i];
    }
    
    public static void main(String[] args) {
        int[] a = { 11, 8, 3, 6, 4, 7, 99, 14 };
        int len = new LIS_Solution().LIS(a);
        System.out.println("最长递增子序列的长度为: " + len);
    }
}
